package leetcode.code0958;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.tree.TreeNode;

//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
//
//内存消耗：37.6 MB, 在所有 Java 提交中击败了78.27%的用户
//
//通过测试用例：119 / 119
public class Solution implements IDebug {

	public boolean isCompleteTree(TreeNode root) {
		boolean stop = false;// stop==true时不允许出现叶子节点
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			TreeNode tn = queue.poll();
			if (stop) {// stop==true时不允许出现叶子节点
				if (tn.left != null || tn.right != null)
					return false;// 出现叶子就false
				else
					continue;// 全空直接continue检查队列中的节点
			}
			if (tn.left != null) {
				queue.add(tn.left);// 不空排队
			} else {
				stop = true;// 自此节点之后队列里不允许出现叶子
			}
			if (!stop && tn.right != null) {// 没停还可以继续添加叶子排队
				queue.add(tn.right);
			} else if (stop && tn.right != null) {
				return false;// 左边没有出现右边，return false
			} else {
				stop = true;// 自此节点之后队列里不允许出现叶子
			}
		}
		return true;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
